import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/** A class used to check if a board can be finished.
 * 	It is not recommended to use it on big boards with many boxes, as checker's complexity is O(board_size ^ number_of_boxes).<br>
 *  However, Checker can serialize informations required for him to compute results very fast.<br>
 *  While Checker requires quite much virtual memory during computing results, informations serialized by it require significantly less memory on hard drive.<br>
 *  It is highly recommended to use Checker to create data files for complicated boards and using checker with these files, rather than computing results during playing.<br>
 *  @author crezax
 */

public class Checker {
	private HashMap<BoardState,Boolean> vis = new HashMap<BoardState,Boolean>();
	private Board checkerBoard, board;
	private boolean done = false, work = true, outOfMemory = false;
	
	/**
     * Constructor that creates a new checker, that will compute results for given board.<br>
     * The results are computed in a new daemon thread created by the constructor.<br>
     * Created thread is set to have lower priority than a thread creating Checker instance.<br>
     * Unfortunately, computing results for a board has exponential complexity.<br>
     *
     * @param board Board to be operated on
     */
	public Checker(final Board board){
		this.board = board;
		final Thread t = new Thread(){
			public void run(){
				Queue<BoardState> K = new LinkedList<BoardState>(), Q = new LinkedList<BoardState>();
				BoardState b = new BoardState(board), actState = null;
				checkerBoard = new Board(board);
				vis.put(b, false);
				K.offer(b);
				while(work && K.peek() != null){
					actState = K.poll();
					checkerBoard.modifyPositions(actState);
					if (checkerBoard.isFinished() == true) {
						Q.offer(actState);
						vis.put(actState, true);
						continue;
					}
					loadNextStates(actState, K);
				}
				while(work && Q.peek() != null){
					actState = Q.poll();
					loadVisitedPreviousStates(actState, Q);
				}
				if (work == false) return;
				work = false;
				done = true;
				System.out.println("While computing, Checker required to keep " + vis.size() + " objects.");
				LinkedList <BoardState> failStates = new LinkedList<BoardState>();
				for (BoardState bS : vis.keySet()){
					if (vis.get(bS) == false) failStates.add(bS);
				}
				for (BoardState bS : failStates){
					vis.remove(bS);
				}
				failStates.clear();
				System.out.println("Checker requires to serialize just " + vis.size() + " objects in to be ready to check this board.");
				//System.out.println("NEXT VERSION WILL REQUIRE LESS STATES TO WORK");
			}
		};
		t.setDaemon(true);
		t.setPriority(Thread.currentThread().getPriority()-2);
		t.start();
		Thread u = new Thread(){
			public void run(){
				Runtime runtime = Runtime.getRuntime();
				
				while(work){
					if ((runtime.freeMemory() + runtime.maxMemory() - runtime.totalMemory()) < 10485760) {
						work = false;
						outOfMemory = true;
						done = true;
						return;
					}
				}
			}
		};
		u.setPriority(t.getPriority()-1);
		u.setDaemon(true);
		u.start();
	}

	/**
     * Constructor that creates a new checker operating on serialized informations created by saveCheckerData method earlier in the past.
     * If the given file is correct, checker will compute results in O(board_size) complexity.
     * This ensures that delay in computing results will be unnoticeable.
     *
     * @param f Reference to file containing serialized checker information.
     * @throws FileNotFoundException
     * @throws IOException
     * @throws ClassNotFoundException if given file doesn't contain serialized informations.
     */
	@SuppressWarnings("unchecked")
	public Checker(File f) throws FileNotFoundException, IOException, ClassNotFoundException{
		ObjectInputStream i = new ObjectInputStream(new FileInputStream(f));
		vis = (HashMap<BoardState, Boolean>) i.readObject();
	}

	/**
     * A function, that checks whether it is possible to finish the board starting at current state
     *
     * @return -1 if it hasn't been checked yet<br>0 if it's not possible<br>1 if it's possible
	 * @throws ComputingFailedException If Checker failed to compute result.
     */
	public int check() throws ComputingFailedException{
		if (outOfMemory) throw new ComputingFailedException();
		Boolean result = vis.get(new BoardState(board));
		if (done == true){
			if (result == null) return 0;
			if (result == false) return 0;
		}
		if (done == false){
			if (result == null) return -1;
			if (result == false) return -1;
		}
		return 1;
	}
	
	/**
     * A function that serializes checker's computing results.
     *
     * @param f File that the results will be written to.
     * @throws FileNotFoundException
     * @throws IOException
     * @throws ComputingNotFinishedException If method is invoked during computing.
	 * @throws ComputingFailedException If Checker failed to compute results.
     */
	public void saveCheckerData(File f) throws FileNotFoundException, IOException, ComputingNotFinishedException, ComputingFailedException{
		if (!done) throw new ComputingNotFinishedException();
		if (outOfMemory) throw new ComputingFailedException();
		ObjectOutputStream o = new ObjectOutputStream(new FileOutputStream(f));
		o.writeObject(vis);
	}

	/**
     * A function used to stop checker during computing.
     *
     * @throws ComputingAlreadyFinishedException
     */
	public void stop() throws ComputingAlreadyFinishedException{
		if (work == false) throw new ComputingAlreadyFinishedException();
		work = false;
	}
	
	/**
     * A function used to check if checker is still computing.
     *
     * @return true if checker is still computing, false otherwise
     */
	public boolean isComputing(){
		return work;
	}
	
	/**
	 * A method that offers states directly reachable from actState to object k implementing Queue interface.
	 * @param actState State states directly reachable from will be offered.
	 * @param k Object that new states will be offered to.
	 */
	private void loadNextStates(BoardState actState, Queue<BoardState> k) {
		//System.out.println("GETTING NEW STATES FROM THIS BOARD:");
		//p(new Board(checkerBoard, actState));
		for (int i=0; i<checkerBoard.getPlayers().length; i++)
			for (Direction j : Direction.values()){
				checkerBoard.modifyPositions(actState);
				//p(checkerBoard);
				//System.out.println("LETS MOVE " + j);
				checkerBoard.getPlayer(i).move(j);
				//p(checkerBoard);
				BoardState testedState = new BoardState(checkerBoard);
				if (vis.containsKey(testedState) == false){
					k.offer(testedState);
					vis.put(testedState, false);
				}
			}
	}

	/** 
	 * A method that offers states actState was directly reachable from to object k implementing Queue interface.
	 * @param actState States that can directly reach this state will be offered.
	 * @param k Object that new states will be offered to.
	 */
	private void loadVisitedPreviousStates(BoardState actState, Queue<BoardState> k) {
		for (int i=0; i<checkerBoard.getPlayers().length; i++)
			for (Direction j : Direction.values()){
				boolean didIPull = false;
				checkerBoard.modifyPositions(actState);
				if (checkerBoard.getPlayer(i).pullBack(j)) didIPull = true;
				BoardState testedState = new BoardState(checkerBoard);
				if (vis.containsKey(testedState) == true && vis.get(testedState) == false){
					k.offer(testedState);
					vis.put(testedState, true);
				}
				if (didIPull){
					checkerBoard.modifyPositions(actState);
					checkerBoard.getPlayer(i).moveWithoutPushing(j);
					testedState = new BoardState(checkerBoard);
					if (vis.containsKey(testedState) == true && vis.get(testedState) == false){
						k.offer(testedState);
						vis.put(testedState, true);
					}
				}
			}
	}
}
